package com.zang.tree;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author ZVerify
 * @since 2022/10/31 08:56
 * @see <a href="https://leetcode.cn/problems/sum-of-left-leaves/">...</a>
 **/
public class 左叶子之和 {

    public int sumOfLeftLeaves(TreeNode root) {

        if (root==null) return 0;
        Deque<TreeNode> list = new LinkedList<>();
        list.add(root);
        int sum = 0;
        while (!list.isEmpty()) {
            int size = list.size();
            for (int i = 0; i < size; i++) {
                TreeNode treeNode = list.pollFirst();
                // 如果为当前行的第一个节点，并且左右都为null说明为左叶子
                if (i==0 && treeNode.left==null && treeNode.right==null) {
                    sum+=treeNode.val;
                }
                if (treeNode.left!=null) list.addLast(treeNode.left);
                if (treeNode.right!=null) list.addLast(treeNode.right);
            }
        }
        return sum;
    }
}
